package offerbook.Code25_pathInBT;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * <p>
 * 1
 * /   \
 * 2     3
 * \
 * 5
 * <p>
 * 输出: ["1->2->5", "1->3"]
 * <p>
 * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 * <p>
 *
 * @date 2020/3/9 18:48
 */
public class Code01_FindAllPath1_leetcode257 {
    public static List<String> findAllPath(TreeNode treeNode) {
        List<String> totalPath = new ArrayList<>();
        if (treeNode == null) {
            return totalPath;
        }
        preInOder(treeNode, totalPath, "");
        return totalPath;
    }

    private static void preInOder(TreeNode root, List<String> totalPath,String path) {
        if (root == null) {
            return;
        }
        //前序遍历要处理的当前节点
        path += String.valueOf(root.val);
        //如果是叶子节点，那么把当前路径加入,
        if (root.left == null && root.right == null) {
            //要开启新的点
            totalPath.add(path);
            //注意这里不要加return，不然导致当前叶子节点无法被及时删除。并且如果在这里删除节点，那么只能删除叶子节点，会出错
        } else {
            path += "->";
            preInOder(root.left, totalPath, path);
            preInOder(root.right, totalPath, path);
        }
    }
    //画图体现
    public static List<String> findAllPath2(TreeNode root) {
        LinkedList<String> paths = new LinkedList();
        if (root == null)
            return paths;
        LinkedList<TreeNode> node_stack = new LinkedList();
        LinkedList<String> path_stack = new LinkedList();
        node_stack.add(root);
        path_stack.add(Integer.toString(root.val));
        TreeNode node;
        String path;
        while (!node_stack.isEmpty()) {
            node = node_stack.pop();
            path = path_stack.pop();
            if ((node.left == null) && (node.right == null))
                paths.add(path);
            if (node.right != null) {
                node_stack.add(node.right);
                path_stack.add(path + "->" + Integer.toString(node.right.val));
            }

            if (node.left != null) {
                node_stack.add(node.left);
                path_stack.add(path + "->" + Integer.toString(node.left.val));
            }
        }
        return paths;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(12);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(7);
        TreeUtil.printTree(root);
        List<String> totalPath = findAllPath(root);
        System.out.println(totalPath);
    }
}
